package LinkedList;//给定一个单链表 L 的头节点 head ，单链表 L 表示为：
//
// 
//L0 → L1 → … → Ln - 1 → Ln
// 
//
// 请将其重新排列后变为： 
//
// 
//L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 
//
// 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：head = [1,2,3,4]
//输出：[1,4,2,3] 
//
// 示例 2： 
//
// 
//
// 
//输入：head = [1,2,3,4,5]
//输出：[1,5,2,4,3] 
//
// 
//
// 提示： 
//
// 
// 链表的长度范围为 [1, 5 * 10⁴] 
// 1 <= node.val <= 1000 
// 
// Related Topics 栈 递归 链表 双指针 👍 889 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class reorderList {
    public void reorderList(ListNode head) {
        if(head==null || head.next==null){
            return;
        }

        //链表切半分为前半部分A，后半部分B,然后逆转后半部分B每隔一个插到链表A
        ListNode curHead = head;
        //找到中间节点
        ListNode pre = curHead, slow = curHead, fast = curHead;
        while(fast!=null && fast.next!=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //截断
        pre.next = null;
        //A 头为 curHead B头为slow
        ListNode B = reverse(slow);
        ListNode A = curHead;
        //将B每隔一个插到A中
        while(A!=null && B!=null){
            //插入
            ListNode tempA = A.next;
            ListNode tempB = B.next;
            A.next = B;
            B.next = tempA;
            B = tempB;
            A = A.next.next;
        }
        //奇数时，A先结束，最后将B连起来
        ListNode c = head;
        while(c.next!=null){
            c = c.next;
        }
        c.next = B;

    }

    private ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode curr = head;
        while(curr!=null){
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;

        }
        return pre;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
